package code.jzh.compiler.scanner;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;

import code.jzh.compiler.util.Constants;

public class NFA {
	public static int idGenerator = 1;
	public NFAState start, end;
	
	public Set<NFAState> nfaStates = new HashSet<NFAState>();
	
	public static NFA buildNFA(String regularStr) {
		Stack<NFA> nfaValueStack = new Stack<NFA>();
		for(int i=0; i<regularStr.length(); i++) {
			char c = regularStr.charAt(i);
			if(c==Constants.escape) {
				c = regularStr.charAt(++i);
				nfaValueStack.push(generateNFABySingleCharacter(c));
					
			}else if(!Constants.isOperator(c)) {//非操作字符，构造nfa入栈
				nfaValueStack.push(generateNFABySingleCharacter(c));
			}else {
				NFA nfaLeft=null, nfaRight=null;
				if(c==Constants.star) {
					nfaLeft = nfaValueStack.pop();
				}else {
					nfaRight = nfaValueStack.pop();
					nfaLeft = nfaValueStack.pop();
				}
				NFA nfa = mergeNFA(nfaLeft, nfaRight, c);
				nfaValueStack.push(nfa);
			}
		}
		NFA finalNFA = nfaValueStack.pop();
		finalNFA.end.accepted = true;
		finalNFA.start.started = true;
		return finalNFA;
	}
	
	public static NFA generateNFABySingleCharacter(char c) {
		NFA nfa = new NFA();
		NFAState start = new NFAState(idGenerator++);
		NFAState end = new NFAState(idGenerator++);
		start.addEdge(c, end.id);
		nfa.start = start;
		nfa.end = end;
		nfa.nfaStates.add(start);
		nfa.nfaStates.add(end);
		return nfa;
	}
	
	public static NFA mergeNFA(NFA nfaLeft, NFA nfaRight, char c) {
		NFA nfa = new NFA();
		switch(c) {
		case Constants.concatenation:
			nfaLeft.end.addEdge(Constants.epsilon, nfaRight.start.id);
			nfa.start = nfaLeft.start;
			nfa.end = nfaRight.end;
			
			nfa.nfaStates.addAll(nfaLeft.nfaStates);
			nfa.nfaStates.addAll(nfaRight.nfaStates);
			break;
			
		case Constants.union:
			NFAState start = new NFAState(idGenerator++);
			NFAState end = new NFAState(idGenerator++);
			
			start.addEdge(Constants.epsilon, nfaLeft.start.id);
			start.addEdge(Constants.epsilon, nfaRight.start.id);
			
			nfaLeft.end.addEdge(Constants.epsilon, end.id);
			nfaRight.end.addEdge(Constants.epsilon, end.id);
			
			nfa.start = start;
			nfa.end = end;
			nfa.nfaStates.addAll(nfaLeft.nfaStates);
			nfa.nfaStates.addAll(nfaRight.nfaStates);
			nfa.nfaStates.add(start);
			nfa.nfaStates.add(end);
			break;
			
		case Constants.star:
			NFAState start2 = new NFAState(idGenerator++);
			NFAState end2 = new NFAState(idGenerator++);
			
			nfaLeft.end.addEdge(Constants.epsilon, nfaLeft.start.id);
			start2.addEdge(Constants.epsilon, nfaLeft.start.id);
			start2.addEdge(Constants.epsilon, end2.id);
			nfaLeft.end.addEdge(Constants.epsilon, end2.id);
			
			nfa.start = start2;
			nfa.end = end2;
			nfa.nfaStates.addAll(nfaLeft.nfaStates);
			nfa.nfaStates.add(start2);
			nfa.nfaStates.add(end2);
			break;
		}
		
		return nfa;
	}
	
	public Set<NFAState> epsilonClosure(Set<NFAState> origin) {
		Set<NFAState> dest = new HashSet<NFAState>();
		if(origin==null || origin.size()==0)
			return dest;
		dest.addAll(origin);
		for(NFAState nfaState : origin) {
			Queue<NFAState> queue = new LinkedList<NFAState>();
			queue.add(nfaState);
			while(!queue.isEmpty()) {
				NFAState curState = queue.poll();
				Set<Integer> charEdges = curState.edges.get(Constants.epsilon);//curState经过字符c能达到的nfa状态的id集合
				if( charEdges==null )
					continue;
				for(int id : charEdges) {
					NFAState charEdgeState = getNFAStateById(id);
					if(!dest.contains(charEdgeState)) {
						dest.add(charEdgeState);
						queue.add(charEdgeState);
					}
				}
			}
		}
		return dest;
	}
	
	public Set<NFAState> deltaCharClosure(Set<NFAState> origin, char c){
		Set<NFAState> dest = new HashSet<NFAState>();
		for(NFAState nfaState : origin) {
			Set<Integer> charEdges = nfaState.edges.get(c);//nfaState经过字符c能达到的nfa状态的id集合
			if( charEdges==null )
				continue;
			for(int id : charEdges) {
				NFAState charEdgeState = getNFAStateById(id);
				dest.add(charEdgeState);
			}
		}
		return dest;
	}
	
	public NFAState getNFAStateById(int id) {
		for(NFAState state : nfaStates)
			if(state.id == id)
				return state;
		return null;
	}
	
	public void printNFA() {
		for(NFAState nfaState : nfaStates) {
			System.out.println("NFA STATE: "+nfaState.id
					+(nfaState.accepted?"\taccepted!!!":"")
					+(nfaState.started?"\tstarted!!!":""));
			for(char c : nfaState.edges.keySet()) {
				for(int id : nfaState.edges.get(c))
					System.out.println("\t"+nfaState.id+"->"+c+"->"+id);
			}
		}
	}
	
	public void printEpsilonClosure(Set<NFAState> states) {
		Set<NFAState> epsilonClosure = epsilonClosure(states);
		for(NFAState epsilonState : epsilonClosure)
			System.out.print(epsilonState.id+"\t");
		System.out.println();
	}
	
	public void testEpsilonClosure() {
		Set<NFAState> startSet = new HashSet<NFAState>();
		startSet.add(start);
		printEpsilonClosure(deltaCharClosure(epsilonClosure(deltaCharClosure(startSet, 'a')),'b'));
	}
}